\begin{abstract}
Motivated by the increasing need for fast distributed processing of  large-scale graphs such as the Web graph and various social networks, we study 
a number of fundamental  graph problems in the message-passing model,
where we have $k$ machines that jointly perform computation on an arbitrary $n$-node (typically, $n \gg k$) input graph. The graph is  assumed to be {\em randomly}  partitioned
  among the $k  \geq 2$ machines (a common implementation in many real world systems). 
 The communication is point-to-point, and the goal
is to minimize the  time complexity, i.e., the number of communication rounds, of solving various fundamental graph problems. 
  

We present lower bounds that quantify the fundamental time limitations of distributively solving graph  problems. 
 We first show a lower bound of
$\Omega(n/k)$ rounds for  computing a spanning tree (ST) of the input graph. This result also implies the same bound for other fundamental problems
such as computing a minimum spanning tree (MST), breadth-first tree (BFS), and shortest paths tree (SPT).    We also show an
$\Omega(n/k^2)$ lower bound for connectivity, ST verification and other related problems. Our lower bounds develop and use new bounds in  {\em random-partition} communication complexity.
 
To complement our lower bounds, we also  give  algorithms for various fundamental graph problems, e.g., PageRank, MST, connectivity, ST verification, shortest paths, cuts, spanners, covering problems, densest subgraph, subgraph isomorphism, finding triangles, etc. We show that problems such as PageRank, MST,  connectivity, and graph covering  can be solved in $\tilde{O}(n/k)$ time 
(the notation $\tilde O$ hides $\text{polylog}(n)$ factors and an additive $\text{polylog}(n)$ term); this shows that one can achieve almost {\em linear} (in $k$) speedup, whereas
 for shortest paths, we present  algorithms that run in $\tilde{O}(n/\sqrt{k})$ time (for $(1+\epsilon)$-factor approximation) and in $\tilde{O}(n/k)$ time (for $O(\log n)$-factor approximation) respectively.

Our results are a step towards  understanding  the complexity of distributively solving large-scale graph problems.

%\medskip


%\noindent {\bf Keywords:} Distributed computing, Large-scale graphs, Graph algorithms,  Time complexity,  Lower bounds.

\end{abstract}
